class Solution {
public:
    int countSubstrings(string s) {
        int n = s.size();
        vector<vector<bool>>dp (n, vector<bool>(n, false));
        int ret = 0;

        for (int j = 0; j < n; j++)
        {
            for (int i = j; i >= 0; i--)
            {
                if (i == j)
                {
                    ret++;
                    dp[i][j] = true;
                }
                else if (s[j] == s[i] && (j - i == 1 || dp[i + 1][j - 1] == 1))
                {
                    ret++;
                    dp[i][j] = true;
                }
            }
        }

        return ret;
    }
};